Методи сортування

Інформація про навчальний заклад

ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано

Інформація про роботу

Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів

Частина тексту файла

Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» ЗВІТ до лабораторної роботи № 3 з дисципліни «Програмування складних алгоритмів» Тема «Методи сортування» Варіант № 24 Дата «12» квітня 2022 Лабораторна робота № 3: Мета роботи: Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування. Завдання до роботи Методичні вказівки Лабораторна робота спирається на знаннях отриманих при вивченні наступних питань лекції: – Поняття сортування. – Різних методів сортування. Завдання до лабораторної роботи: Розробити програму з алгоритмом згідно варіанту з використанням методів сортування. Оцінити час виконання та складність алгоритму. 1. Провести сортування масивів вказаним методом та у вказаному порядку. Для тестування алгоритмів сортування масив (10x10, та більше бажанням). 2. Самостійно обрати додатковий метод та провести сортування того ж масиву. 3. Порівняти кількість перестановок (або час виконання) обох методів. Спробувати порівняти час виконання сортування з масивом більшого розміру, який створити за допомогою генератора випадкових чисел Завдання / / 1.2. Теоретичні відомості Алгоритм сортування— процес, що впорядковує множину однотипних елементів за певною ознакою (ключем сортування). Сортування є типовою проблемою обробки даних, що забезпечує розміщення елементів невпорядкованого набору значень в порядку монотонного зростання або спадання значення ключа. Основні методи сортування масивів: Бульбашкове сортування — у вхідній послідовності порівнюються два сусідні елементи і, якщо вони не відповідають критерію сортування, ці елементи міняються місцями. Алгоритм працює доти, доки весь масив даних не буде впорядковано. Часова складність — O(n2). Сортування вставками — елементи вхідної послідовності проглядаються по одному, і кожен новий елемент, що надійшов, розміщується в придатне місце серед раніше упорядкованих елементів. Застосовується для майже цілком відсортованих даних та даних невеликого розміру. Часова складність — O(n2). Сортування вибором — поєднання бульбашкового сортування та сортування вставками. Як і у бульбашкового сортування, цей алгоритм проходить масивом раз за разом, переміщаючи одне значення на правильну позицію. Однак, на відміну від бульбашкового сортування, вибирає найменше невідсортоване значення замість найбільшого. Як і при сортуванні вставками, упорядкована частина масиву розташована на початку, тоді як у бульбашкового сортування — наприкінці. Часова складність — O(n2). Швидке сортування — алгоритм, який не потребує додаткової пам’яті, оскільки використовує прості цикли й операції, працює швидше за інші алгоритми, що мають таку ж асимптотичну оцінку складності. З масиву обирається опорний елемент, і весь масив розбивається на дві частини: в першій — елементи, не більші даного, в другій — не менші. Впорядкування кожної з частин відбувається рекурсивно. Час роботи алгоритму сортування залежить від того, який елемент обрано як опорний. У найгіршому випадку час роботи алгоритму — O(n2), але математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах ближче до найкращого — O(n log n). 1.3. Результати роботи Завдання 1. Написано програмний код, який реалізує задачу відсортувати масив відповідно до наданого зразку. Сортування здійснюється за допомогою обмінного методу quickSort. Для порівняння швидкості роботи алгоритму додатково розроблено метод сортування bubbleSort.. У найгіршому випадку часова складність першого алгоритму — O(n2), але математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах ближче до найкращого — O(n log n). Часова складність другого алгоритму — O(n2). Нижче в таблиці представлено залежність часу виконання від розмірів масиву та відповідно кількості ітерацій. Спосіб сортування Розмір N*M Час виконання   Бульбашкове сортування 10*10 0,011 ms   1000*1000 131,592 ms   Швидке сортування 10*10 0,015 ms ...
Антиботан аватар за замовчуванням

09.05.2023 18:05

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини